/*
 * Copyright (c) Kumo Inc. and affiliates.
 * Copyright (c) Meta Platforms, Inc. and affiliates.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include <melon/json/json_schema.h>

#include <boost/algorithm/string/replace.hpp>
#include <boost/regex.hpp>

#include <melon/cportability.h>
#include <melon/conv.h>
#include <melon/memory.h>
#include <melon/optional.h>
#include <melon/singleton.h>
#include <melon/string.h>
#include <melon/json/json.h>
#include <melon/portability/math.h>

namespace melon {
    namespace jsonschema {
        namespace {
            /**
             * We throw this exception when schema validation fails.
             */
            struct MELON_EXPORT SchemaError : std::runtime_error {
                SchemaError(SchemaError &&) = default;

                SchemaError(const SchemaError &) = default;

                SchemaError(melon::StringPiece expected, const Dynamic &value)
                    : std::runtime_error(to<std::string>(
                        "Expected to get ", expected, " for value ", toJson(value))) {
                }

                SchemaError(
                    melon::StringPiece expected, const Dynamic &schema, const Dynamic &value)
                    : std::runtime_error(to<std::string>(
                        "Expected to get ",
                        expected,
                        toJson(schema),
                        " for value ",
                        toJson(value))) {
                }
            };

            template<class... Args>
            Optional<SchemaError> makeError(Args &&... args) {
                return Optional<SchemaError>(SchemaError(std::forward<Args>(args)...));
            }

            struct ValidationContext;

            struct IValidator {
                virtual ~IValidator() = default;

            private:
                friend struct ValidationContext;

                virtual Optional<SchemaError> validate(
                    ValidationContext &, const Dynamic &value) const = 0;
            };

            /**
             * This is a 'context' used only when executing the validators to validate some
             * json. It keeps track of which validators have been executed on which json so
             * we can detect infinite recursion.
             */
            struct ValidationContext {
                Optional<SchemaError> validate(IValidator *validator, const Dynamic &value) {
                    auto ret = seen.insert(std::make_pair(validator, &value));
                    if (!ret.second) {
                        throw std::runtime_error("Infinite recursion detected");
                    }
                    return validator->validate(*this, value);
                }

            private:
                std::unordered_set<std::pair<const IValidator *, const Dynamic *> > seen;
            };

            /**
             * This is a 'context' used only when building the schema validators from a
             * piece of json. It stores the original schema and the set of refs, so that we
             * can have parts of the schema refer to other parts.
             */
            struct SchemaValidatorContext final {
                explicit SchemaValidatorContext(const Dynamic &s) : schema(s) {
                }

                const Dynamic &schema;
                std::unordered_map<std::string, IValidator *> refs;
            };

            /**
             * Root validator for a schema.
             */
            struct SchemaValidator final : IValidator, public Validator {
                SchemaValidator() = default;

                void loadSchema(SchemaValidatorContext &context, const Dynamic &schema);

                Optional<SchemaError> validate(
                    ValidationContext &, const Dynamic &value) const override;

                // Validator interface
                void validate(const Dynamic &value) const override;

                exception_wrapper try_validate(const Dynamic &value) const noexcept override;

                static std::unique_ptr<SchemaValidator> make(
                    SchemaValidatorContext &context, const Dynamic &schema) {
                    // We break apart the constructor and actually loading the schema so that
                    // we can handle the case where a schema refers to itself, e.g. via
                    // "$ref": "#".
                    auto v = std::make_unique<SchemaValidator>();
                    v->loadSchema(context, schema);
                    return v;
                }

            private:
                std::vector<std::unique_ptr<IValidator> > validators_;
            };

            struct MultipleOfValidator final : IValidator {
                explicit MultipleOfValidator(Dynamic schema) : schema_(std::move(schema)) {
                }

                Optional<SchemaError> validate(
                    ValidationContext &, const Dynamic &value) const override {
                    if (!schema_.isNumber() || !value.isNumber()) {
                        return none;
                    }
                    if (schema_.isDouble() || value.isDouble()) {
                        const auto rem = melon::remainder(value.asDouble(), schema_.asDouble());
                        if (std::abs(rem) > std::numeric_limits<double>::epsilon()) {
                            return makeError("a multiple of ", schema_, value);
                        }
                    } else {
                        // both ints
                        if ((value.getInt() % schema_.getInt()) != 0) {
                            return makeError("a multiple of ", schema_, value);
                        }
                    }
                    return none;
                }

                Dynamic schema_;
            };

            struct ComparisonValidator final : IValidator {
                enum class Type { MIN, MAX };

                ComparisonValidator(Dynamic schema, const Dynamic *exclusive, Type type)
                    : schema_(std::move(schema)), exclusive_(false), type_(type) {
                    if (exclusive && exclusive->isBool()) {
                        exclusive_ = exclusive->getBool();
                    }
                }

                template<typename Numeric>
                Optional<SchemaError> validateHelper(
                    const Dynamic &value, Numeric s, Numeric v) const {
                    if (type_ == Type::MIN) {
                        if (exclusive_) {
                            if (v <= s) {
                                return makeError("greater than ", schema_, value);
                            }
                        } else {
                            if (v < s) {
                                return makeError("greater than or equal to ", schema_, value);
                            }
                        }
                    } else if (type_ == Type::MAX) {
                        if (exclusive_) {
                            if (v >= s) {
                                return makeError("less than ", schema_, value);
                            }
                        } else {
                            if (v > s) {
                                return makeError("less than or equal to ", schema_, value);
                            }
                        }
                    }
                    return none;
                }

                Optional<SchemaError> validate(
                    ValidationContext &, const Dynamic &value) const override {
                    if (!schema_.isNumber() || !value.isNumber()) {
                        return none;
                    }
                    if (schema_.isDouble() || value.isDouble()) {
                        return validateHelper(value, schema_.asDouble(), value.asDouble());
                    } else {
                        // both ints
                        return validateHelper(value, schema_.asInt(), value.asInt());
                    }
                }

                Dynamic schema_;
                bool exclusive_;
                Type type_;
            };

            template<class Comparison>
            struct SizeValidator final : IValidator {
                explicit SizeValidator(const Dynamic &schema, Dynamic::Type type)
                    : length_(-1), type_(type) {
                    if (schema.isInt()) {
                        length_ = schema.getInt();
                    }
                }

                Optional<SchemaError> validate(
                    ValidationContext &, const Dynamic &value) const override {
                    if (length_ < 0) {
                        return none;
                    }
                    if (value.type() != type_) {
                        return none;
                    }
                    if (!Comparison()(length_, int64_t(value.size()))) {
                        return makeError("different length string/array/object", value);
                    }
                    return none;
                }

                int64_t length_;
                Dynamic::Type type_;
            };

            struct StringPatternValidator final : IValidator {
                explicit StringPatternValidator(const Dynamic &schema) {
                    if (schema.isString()) {
                        regex_ = boost::regex(schema.getString());
                    }
                }

                Optional<SchemaError> validate(
                    ValidationContext &, const Dynamic &value) const override {
                    if (!value.isString() || regex_.empty()) {
                        return none;
                    }
                    if (!boost::regex_search(value.getString(), regex_)) {
                        return makeError("string matching regex", value);
                    }
                    return none;
                }

                boost::regex regex_;
            };

            struct ArrayUniqueValidator final : IValidator {
                explicit ArrayUniqueValidator(const Dynamic &schema) : unique_(false) {
                    if (schema.isBool()) {
                        unique_ = schema.getBool();
                    }
                }

                Optional<SchemaError> validate(
                    ValidationContext &, const Dynamic &value) const override {
                    if (!unique_ || !value.isArray()) {
                        return none;
                    }
                    for (const auto &i: value) {
                        for (const auto &j: value) {
                            if (&i != &j && i == j) {
                                return makeError("unique items in array", value);
                            }
                        }
                    }
                    return none;
                }

                bool unique_;
            };

            struct ArrayItemsValidator final : IValidator {
                ArrayItemsValidator(
                    SchemaValidatorContext &context,
                    const Dynamic *items,
                    const Dynamic *additionalItems)
                    : allowAdditionalItems_(true) {
                    if (items && items->isObject()) {
                        itemsValidator_ = SchemaValidator::make(context, *items);
                        return; // Additional items is ignored
                    } else if (items && items->isArray()) {
                        for (const auto &item: *items) {
                            itemsValidators_.emplace_back(SchemaValidator::make(context, item));
                        }
                    } else {
                        // If items isn't present or is invalid, it defaults to an empty schema.
                        itemsValidator_ = SchemaValidator::make(context, Dynamic::object);
                    }
                    if (additionalItems) {
                        if (additionalItems->isBool()) {
                            allowAdditionalItems_ = additionalItems->getBool();
                        } else if (additionalItems->isObject()) {
                            additionalItemsValidator_ =
                                    SchemaValidator::make(context, *additionalItems);
                        }
                    }
                }

                Optional<SchemaError> validate(
                    ValidationContext &vc, const Dynamic &value) const override {
                    if (!value.isArray()) {
                        return none;
                    }
                    if (itemsValidator_) {
                        for (const auto &v: value) {
                            if (auto se = vc.validate(itemsValidator_.get(), v)) {
                                return se;
                            }
                        }
                        return none;
                    }
                    size_t pos = 0;
                    for (; pos < value.size() && pos < itemsValidators_.size(); ++pos) {
                        if (auto se = vc.validate(itemsValidators_[pos].get(), value[pos])) {
                            return se;
                        }
                    }
                    if (!allowAdditionalItems_ && pos < value.size()) {
                        return makeError("no more additional items", value);
                    }
                    if (additionalItemsValidator_) {
                        for (; pos < value.size(); ++pos) {
                            if (auto se =
                                    vc.validate(additionalItemsValidator_.get(), value[pos])) {
                                return se;
                            }
                        }
                    }
                    return none;
                }

                std::unique_ptr<IValidator> itemsValidator_;
                std::vector<std::unique_ptr<IValidator> > itemsValidators_;
                std::unique_ptr<IValidator> additionalItemsValidator_;
                bool allowAdditionalItems_;
            };

            struct RequiredValidator final : IValidator {
                explicit RequiredValidator(const Dynamic &schema) {
                    if (schema.isArray()) {
                        for (const auto &item: schema) {
                            if (item.isString()) {
                                properties_.emplace_back(item.getString());
                            }
                        }
                    }
                }

                Optional<SchemaError> validate(
                    ValidationContext &, const Dynamic &value) const override {
                    if (value.isObject()) {
                        for (const auto &prop: properties_) {
                            if (!value.get_ptr(prop)) {
                                return makeError("property ", prop, value);
                            }
                        }
                    }
                    return none;
                }

            private:
                std::vector<std::string> properties_;
            };

            struct PropertiesValidator final : IValidator {
                PropertiesValidator(
                    SchemaValidatorContext &context,
                    const Dynamic *properties,
                    const Dynamic *patternProperties,
                    const Dynamic *additionalProperties)
                    : allowAdditionalProperties_(true) {
                    if (properties && properties->isObject()) {
                        for (const auto &pair: properties->items()) {
                            if (pair.first.isString()) {
                                propertyValidators_[pair.first.getString()] =
                                        SchemaValidator::make(context, pair.second);
                            }
                        }
                    }
                    if (patternProperties && patternProperties->isObject()) {
                        for (const auto &pair: patternProperties->items()) {
                            if (pair.first.isString()) {
                                patternPropertyValidators_.emplace_back(
                                    boost::regex(pair.first.getString()),
                                    SchemaValidator::make(context, pair.second));
                            }
                        }
                    }
                    if (additionalProperties) {
                        if (additionalProperties->isBool()) {
                            allowAdditionalProperties_ = additionalProperties->getBool();
                        } else if (additionalProperties->isObject()) {
                            additionalPropertyValidator_ =
                                    SchemaValidator::make(context, *additionalProperties);
                        }
                    }
                }

                Optional<SchemaError> validate(
                    ValidationContext &vc, const Dynamic &value) const override {
                    if (!value.isObject()) {
                        return none;
                    }
                    for (const auto &pair: value.items()) {
                        if (!pair.first.isString()) {
                            continue;
                        }
                        const std::string &key = pair.first.getString();
                        auto it = propertyValidators_.find(key);
                        bool matched = false;
                        if (it != propertyValidators_.end()) {
                            if (auto se = vc.validate(it->second.get(), pair.second)) {
                                return se;
                            }
                            matched = true;
                        }

                        const std::string &strkey = key;
                        for (const auto &ppv: patternPropertyValidators_) {
                            if (boost::regex_search(strkey, ppv.first)) {
                                if (auto se = vc.validate(ppv.second.get(), pair.second)) {
                                    return se;
                                }
                                matched = true;
                            }
                        }
                        if (matched) {
                            continue;
                        }
                        if (!allowAdditionalProperties_) {
                            return makeError("no more additional properties", value);
                        }
                        if (additionalPropertyValidator_) {
                            if (auto se =
                                    vc.validate(additionalPropertyValidator_.get(), pair.second)) {
                                return se;
                            }
                        }
                    }
                    return none;
                }

                std::unordered_map<std::string, std::unique_ptr<IValidator> >
                propertyValidators_;
                std::vector<std::pair<boost::regex, std::unique_ptr<IValidator> > >
                patternPropertyValidators_;
                std::unique_ptr<IValidator> additionalPropertyValidator_;
                bool allowAdditionalProperties_;
            };

            struct DependencyValidator final : IValidator {
                DependencyValidator(SchemaValidatorContext &context, const Dynamic &schema) {
                    if (!schema.isObject()) {
                        return;
                    }
                    for (const auto &pair: schema.items()) {
                        if (!pair.first.isString()) {
                            continue;
                        }
                        if (pair.second.isArray()) {
                            auto p = make_pair(pair.first.getString(), std::vector<std::string>());
                            for (const auto &item: pair.second) {
                                if (item.isString()) {
                                    p.second.push_back(item.getString());
                                }
                            }
                            propertyDep_.emplace_back(std::move(p));
                        }
                        if (pair.second.isObject()) {
                            schemaDep_.emplace_back(
                                pair.first.getString(),
                                SchemaValidator::make(context, pair.second));
                        }
                    }
                }

                Optional<SchemaError> validate(
                    ValidationContext &vc, const Dynamic &value) const override {
                    if (!value.isObject()) {
                        return none;
                    }
                    for (const auto &pair: propertyDep_) {
                        if (value.count(pair.first)) {
                            for (const auto &prop: pair.second) {
                                if (!value.count(prop)) {
                                    return makeError("property ", prop, value);
                                }
                            }
                        }
                    }
                    for (const auto &pair: schemaDep_) {
                        if (value.count(pair.first)) {
                            if (auto se = vc.validate(pair.second.get(), value)) {
                                return se;
                            }
                        }
                    }
                    return none;
                }

                std::vector<std::pair<std::string, std::vector<std::string> > > propertyDep_;
                std::vector<std::pair<std::string, std::unique_ptr<IValidator> > > schemaDep_;
            };

            struct EnumValidator final : IValidator {
                explicit EnumValidator(Dynamic schema) : schema_(std::move(schema)) {
                }

                Optional<SchemaError> validate(
                    ValidationContext &, const Dynamic &value) const override {
                    if (!schema_.isArray()) {
                        return none;
                    }
                    for (const auto &item: schema_) {
                        if (value == item) {
                            return none;
                        }
                    }
                    return makeError("one of enum values: ", schema_, value);
                }

                Dynamic schema_;
            };

            struct TypeValidator final : IValidator {
                explicit TypeValidator(const Dynamic &schema) {
                    if (schema.isString()) {
                        addType(schema.stringPiece());
                    } else if (schema.isArray()) {
                        for (const auto &item: schema) {
                            if (item.isString()) {
                                addType(item.stringPiece());
                            }
                        }
                    }
                }

                Optional<SchemaError> validate(
                    ValidationContext &, const Dynamic &value) const override {
                    auto it =
                            std::find(allowedTypes_.begin(), allowedTypes_.end(), value.type());
                    if (it == allowedTypes_.end()) {
                        return makeError("a value of type ", typeStr_, value);
                    }
                    return none;
                }

            private:
                std::vector<Dynamic::Type> allowedTypes_;
                std::string typeStr_; // for errors

                void addType(StringPiece value) {
                    if (value == "array") {
                        allowedTypes_.push_back(Dynamic::Type::ARRAY);
                    } else if (value == "boolean") {
                        allowedTypes_.push_back(Dynamic::Type::BOOL);
                    } else if (value == "integer") {
                        allowedTypes_.push_back(Dynamic::Type::INT64);
                    } else if (value == "number") {
                        allowedTypes_.push_back(Dynamic::Type::INT64);
                        allowedTypes_.push_back(Dynamic::Type::DOUBLE);
                    } else if (value == "null") {
                        allowedTypes_.push_back(Dynamic::Type::NULLT);
                    } else if (value == "object") {
                        allowedTypes_.push_back(Dynamic::Type::OBJECT);
                    } else if (value == "string") {
                        allowedTypes_.push_back(Dynamic::Type::STRING);
                    } else {
                        return;
                    }
                    if (!typeStr_.empty()) {
                        typeStr_ += ", ";
                    }
                    typeStr_ += value.str();
                }
            };

            struct AllOfValidator final : IValidator {
                AllOfValidator(SchemaValidatorContext &context, const Dynamic &schema) {
                    if (schema.isArray()) {
                        for (const auto &item: schema) {
                            validators_.emplace_back(SchemaValidator::make(context, item));
                        }
                    }
                }

                Optional<SchemaError> validate(
                    ValidationContext &vc, const Dynamic &value) const override {
                    for (const auto &val: validators_) {
                        if (auto se = vc.validate(val.get(), value)) {
                            return se;
                        }
                    }
                    return none;
                }

                std::vector<std::unique_ptr<IValidator> > validators_;
            };

            struct AnyOfValidator final : IValidator {
                enum class Type { EXACTLY_ONE, ONE_OR_MORE };

                AnyOfValidator(
                    SchemaValidatorContext &context, const Dynamic &schema, Type type)
                    : type_(type) {
                    if (schema.isArray()) {
                        for (const auto &item: schema) {
                            validators_.emplace_back(SchemaValidator::make(context, item));
                        }
                    }
                }

                Optional<SchemaError> validate(
                    ValidationContext &vc, const Dynamic &value) const override {
                    std::vector<SchemaError> errors;
                    for (const auto &val: validators_) {
                        if (auto se = vc.validate(val.get(), value)) {
                            errors.emplace_back(*se);
                        }
                    }
                    const auto success = validators_.size() - errors.size();
                    if (success == 0) {
                        return makeError("at least one valid schema", value);
                    } else if (success > 1 && type_ == Type::EXACTLY_ONE) {
                        return makeError("exactly one valid schema", value);
                    }
                    return none;
                }

                Type type_;
                std::vector<std::unique_ptr<IValidator> > validators_;
            };

            struct RefValidator final : IValidator {
                explicit RefValidator(IValidator *validator) : validator_(validator) {
                }

                Optional<SchemaError> validate(
                    ValidationContext &vc, const Dynamic &value) const override {
                    return vc.validate(validator_, value);
                }

                IValidator *validator_;
            };

            struct NotValidator final : IValidator {
                NotValidator(SchemaValidatorContext &context, const Dynamic &schema)
                    : validator_(SchemaValidator::make(context, schema)) {
                }

                Optional<SchemaError> validate(
                    ValidationContext &vc, const Dynamic &value) const override {
                    if (vc.validate(validator_.get(), value)) {
                        return none;
                    }
                    return makeError("Expected schema validation to fail", value);
                }

                std::unique_ptr<IValidator> validator_;
            };

            void SchemaValidator::loadSchema(
                SchemaValidatorContext &context, const Dynamic &schema) {
                if (!schema.isObject() || schema.empty()) {
                    return;
                }

                // Check for $ref, if we have one we won't apply anything else. Refs are
                // pointers to other parts of the json, e.g. #/foo/bar points to the schema
                // located at root["foo"]["bar"].
                if (const auto *p = schema.get_ptr("$ref")) {
                    // We only support absolute refs, i.e. those starting with '#'
                    if (p->isString() && p->stringPiece()[0] == '#') {
                        auto it = context.refs.find(p->getString());
                        if (it != context.refs.end()) {
                            validators_.emplace_back(std::make_unique<RefValidator>(it->second));
                            return;
                        }

                        // This is a ref, but we haven't loaded it yet. Find where it is based on
                        // the root schema.
                        std::vector<std::string> parts;
                        split("/", p->stringPiece(), parts);
                        const auto *s = &context.schema; // First part is '#'
                        for (size_t i = 1; s && i < parts.size(); ++i) {
                            // Per the standard, we must replace ~1 with / and then ~0 with ~
                            boost::replace_all(parts[i], "~1", "/");
                            boost::replace_all(parts[i], "~0", "~");
                            if (s->isObject()) {
                                s = s->get_ptr(parts[i]);
                                continue;
                            }
                            if (s->isArray()) {
                                try {
                                    const size_t pos = to<size_t>(parts[i]);
                                    if (pos < s->size()) {
                                        s = s->get_ptr(pos);
                                        continue;
                                    }
                                } catch (const std::range_error &) {
                                    // ignore
                                }
                            }
                            break;
                        }
                        // If you have a self-recursive reference, this avoids getting into an
                        // infinite recursion, where we try to load a schema that just references
                        // itself, and then we try to load it again, and so on.
                        // Instead we load a pointer to the schema into the refs, so that any
                        // future references to it will just see that pointer and won't try to
                        // keep parsing further.
                        if (s) {
                            auto v = std::make_unique<SchemaValidator>();
                            context.refs[p->getString()] = v.get();
                            v->loadSchema(context, *s);
                            validators_.emplace_back(std::move(v));
                            return;
                        }
                    }
                }

                // Numeric validators
                if (const auto *p = schema.get_ptr("multipleOf")) {
                    validators_.emplace_back(std::make_unique<MultipleOfValidator>(*p));
                }
                if (const auto *p = schema.get_ptr("maximum")) {
                    validators_.emplace_back(std::make_unique<ComparisonValidator>(
                        *p,
                        schema.get_ptr("exclusiveMaximum"),
                        ComparisonValidator::Type::MAX));
                }
                if (const auto *p = schema.get_ptr("minimum")) {
                    validators_.emplace_back(std::make_unique<ComparisonValidator>(
                        *p,
                        schema.get_ptr("exclusiveMinimum"),
                        ComparisonValidator::Type::MIN));
                }

                // String validators
                if (const auto *p = schema.get_ptr("maxLength")) {
                    validators_.emplace_back(
                        std::make_unique<SizeValidator<std::greater_equal<int64_t> > >(
                            *p, Dynamic::Type::STRING));
                }
                if (const auto *p = schema.get_ptr("minLength")) {
                    validators_.emplace_back(
                        std::make_unique<SizeValidator<std::less_equal<int64_t> > >(
                            *p, Dynamic::Type::STRING));
                }
                if (const auto *p = schema.get_ptr("pattern")) {
                    validators_.emplace_back(std::make_unique<StringPatternValidator>(*p));
                }

                // Array validators
                const auto *items = schema.get_ptr("items");
                const auto *additionalItems = schema.get_ptr("additionalItems");
                if (items || additionalItems) {
                    validators_.emplace_back(
                        std::make_unique<ArrayItemsValidator>(context, items, additionalItems));
                }
                if (const auto *p = schema.get_ptr("maxItems")) {
                    validators_.emplace_back(
                        std::make_unique<SizeValidator<std::greater_equal<int64_t> > >(
                            *p, Dynamic::Type::ARRAY));
                }
                if (const auto *p = schema.get_ptr("minItems")) {
                    validators_.emplace_back(
                        std::make_unique<SizeValidator<std::less_equal<int64_t> > >(
                            *p, Dynamic::Type::ARRAY));
                }
                if (const auto *p = schema.get_ptr("uniqueItems")) {
                    validators_.emplace_back(std::make_unique<ArrayUniqueValidator>(*p));
                }

                // Object validators
                const auto *properties = schema.get_ptr("properties");
                const auto *patternProperties = schema.get_ptr("patternProperties");
                const auto *additionalProperties = schema.get_ptr("additionalProperties");
                if (properties || patternProperties || additionalProperties) {
                    validators_.emplace_back(std::make_unique<PropertiesValidator>(
                        context, properties, patternProperties, additionalProperties));
                }
                if (const auto *p = schema.get_ptr("maxProperties")) {
                    validators_.emplace_back(
                        std::make_unique<SizeValidator<std::greater_equal<int64_t> > >(
                            *p, Dynamic::Type::OBJECT));
                }
                if (const auto *p = schema.get_ptr("minProperties")) {
                    validators_.emplace_back(
                        std::make_unique<SizeValidator<std::less_equal<int64_t> > >(
                            *p, Dynamic::Type::OBJECT));
                }
                if (const auto *p = schema.get_ptr("required")) {
                    validators_.emplace_back(std::make_unique<RequiredValidator>(*p));
                }

                // Misc validators
                if (const auto *p = schema.get_ptr("dependencies")) {
                    validators_.emplace_back(
                        std::make_unique<DependencyValidator>(context, *p));
                }
                if (const auto *p = schema.get_ptr("enum")) {
                    validators_.emplace_back(std::make_unique<EnumValidator>(*p));
                }
                if (const auto *p = schema.get_ptr("type")) {
                    validators_.emplace_back(std::make_unique<TypeValidator>(*p));
                }
                if (const auto *p = schema.get_ptr("allOf")) {
                    validators_.emplace_back(std::make_unique<AllOfValidator>(context, *p));
                }
                if (const auto *p = schema.get_ptr("anyOf")) {
                    validators_.emplace_back(std::make_unique<AnyOfValidator>(
                        context, *p, AnyOfValidator::Type::ONE_OR_MORE));
                }
                if (const auto *p = schema.get_ptr("oneOf")) {
                    validators_.emplace_back(std::make_unique<AnyOfValidator>(
                        context, *p, AnyOfValidator::Type::EXACTLY_ONE));
                }
                if (const auto *p = schema.get_ptr("not")) {
                    validators_.emplace_back(std::make_unique<NotValidator>(context, *p));
                }
            }

            void SchemaValidator::validate(const Dynamic &value) const {
                ValidationContext vc;
                if (auto se = validate(vc, value)) {
                    throw *se;
                }
            }

            exception_wrapper SchemaValidator::try_validate(
                const Dynamic &value) const noexcept {
                try {
                    ValidationContext vc;
                    if (auto se = validate(vc, value)) {
                        return make_exception_wrapper<SchemaError>(*se);
                    }
                } catch (...) {
                    return exception_wrapper(current_exception());
                }
                return exception_wrapper();
            }

            Optional<SchemaError> SchemaValidator::validate(
                ValidationContext &vc, const Dynamic &value) const {
                for (const auto &validator: validators_) {
                    if (auto se = vc.validate(validator.get(), value)) {
                        return se;
                    }
                }
                return none;
            }

            /**
             * Metaschema, i.e. schema for schema.
             * Inlined from the $schema url
             */
            const char *metaschemaJson =
                    "\
{ \
    \"id\": \"http://json-schema.org/draft-04/schema#\", \
    \"$schema\": \"http://json-schema.org/draft-04/schema#\", \
    \"description\": \"Core schema meta-schema\", \
    \"definitions\": { \
        \"schemaArray\": { \
            \"type\": \"array\", \
            \"minItems\": 1, \
            \"items\": { \"$ref\": \"#\" } \
        }, \
        \"positiveInteger\": { \
            \"type\": \"integer\", \
            \"minimum\": 0 \
        }, \
        \"positiveIntegerDefault0\": { \
            \"allOf\": [ \
          { \"$ref\": \"#/definitions/positiveInteger\" }, { \"default\": 0 } ]\
        }, \
        \"simpleTypes\": { \
            \"enum\": [ \"array\", \"boolean\", \"integer\", \
                        \"null\", \"number\", \"object\", \"string\" ] \
        }, \
        \"stringArray\": { \
            \"type\": \"array\", \
            \"items\": { \"type\": \"string\" }, \
            \"minItems\": 1, \
            \"uniqueItems\": true \
        } \
    }, \
    \"type\": \"object\", \
    \"properties\": { \
        \"id\": { \
            \"type\": \"string\", \
            \"format\": \"uri\" \
        }, \
        \"$schema\": { \
            \"type\": \"string\", \
            \"format\": \"uri\" \
        }, \
        \"title\": { \
            \"type\": \"string\" \
        }, \
        \"description\": { \
            \"type\": \"string\" \
        }, \
        \"default\": {}, \
        \"multipleOf\": { \
            \"type\": \"number\", \
            \"minimum\": 0, \
            \"exclusiveMinimum\": true \
        }, \
        \"maximum\": { \
            \"type\": \"number\" \
        }, \
        \"exclusiveMaximum\": { \
            \"type\": \"boolean\", \
            \"default\": false \
        }, \
        \"minimum\": { \
            \"type\": \"number\" \
        }, \
        \"exclusiveMinimum\": { \
            \"type\": \"boolean\", \
            \"default\": false \
        }, \
        \"maxLength\": { \"$ref\": \"#/definitions/positiveInteger\" }, \
        \"minLength\": { \"$ref\": \"#/definitions/positiveIntegerDefault0\" },\
        \"pattern\": { \
            \"type\": \"string\", \
            \"format\": \"regex\" \
        }, \
        \"additionalItems\": { \
            \"anyOf\": [ \
                { \"type\": \"boolean\" }, \
                { \"$ref\": \"#\" } \
            ], \
            \"default\": {} \
        }, \
        \"items\": { \
            \"anyOf\": [ \
                { \"$ref\": \"#\" }, \
                { \"$ref\": \"#/definitions/schemaArray\" } \
            ], \
            \"default\": {} \
        }, \
        \"maxItems\": { \"$ref\": \"#/definitions/positiveInteger\" }, \
        \"minItems\": { \"$ref\": \"#/definitions/positiveIntegerDefault0\" }, \
        \"uniqueItems\": { \
            \"type\": \"boolean\", \
            \"default\": false \
        }, \
        \"maxProperties\": { \"$ref\": \"#/definitions/positiveInteger\" }, \
        \"minProperties\": { \
        \"$ref\": \"#/definitions/positiveIntegerDefault0\" }, \
        \"required\": { \"$ref\": \"#/definitions/stringArray\" }, \
        \"additionalProperties\": { \
            \"anyOf\": [ \
                { \"type\": \"boolean\" }, \
                { \"$ref\": \"#\" } \
            ], \
            \"default\": {} \
        }, \
        \"definitions\": { \
            \"type\": \"object\", \
            \"additionalProperties\": { \"$ref\": \"#\" }, \
            \"default\": {} \
        }, \
        \"properties\": { \
            \"type\": \"object\", \
            \"additionalProperties\": { \"$ref\": \"#\" }, \
            \"default\": {} \
        }, \
        \"patternProperties\": { \
            \"type\": \"object\", \
            \"additionalProperties\": { \"$ref\": \"#\" }, \
            \"default\": {} \
        }, \
        \"dependencies\": { \
            \"type\": \"object\", \
            \"additionalProperties\": { \
                \"anyOf\": [ \
                    { \"$ref\": \"#\" }, \
                    { \"$ref\": \"#/definitions/stringArray\" } \
                ] \
            } \
        }, \
        \"enum\": { \
            \"type\": \"array\", \
            \"minItems\": 1, \
            \"uniqueItems\": true \
        }, \
        \"type\": { \
            \"anyOf\": [ \
                { \"$ref\": \"#/definitions/simpleTypes\" }, \
                { \
                    \"type\": \"array\", \
                    \"items\": { \"$ref\": \"#/definitions/simpleTypes\" }, \
                    \"minItems\": 1, \
                    \"uniqueItems\": true \
                } \
            ] \
        }, \
        \"allOf\": { \"$ref\": \"#/definitions/schemaArray\" }, \
        \"anyOf\": { \"$ref\": \"#/definitions/schemaArray\" }, \
        \"oneOf\": { \"$ref\": \"#/definitions/schemaArray\" }, \
        \"not\": { \"$ref\": \"#\" } \
    }, \
    \"dependencies\": { \
        \"exclusiveMaximum\": [ \"maximum\" ], \
        \"exclusiveMinimum\": [ \"minimum\" ] \
    }, \
    \"default\": {} \
}";

            melon::Singleton<Validator> schemaValidator([]() {
                return makeValidator(parseJson(metaschemaJson)).release();
            });
        } // namespace

        Validator::~Validator() = default;

        std::unique_ptr<Validator> makeValidator(const Dynamic &schema) {
            auto v = std::make_unique<SchemaValidator>();
            SchemaValidatorContext context(schema);
            context.refs["#"] = v.get();
            v->loadSchema(context, schema);
            return v;
        }

        std::shared_ptr<Validator> makeSchemaValidator() {
            return schemaValidator.try_get();
        }
    } // namespace jsonschema
} // namespace melon
